package _go

import "sort"

//执行时间和内存 	8 ms	2.8 MB	Go
func fourSum(nums []int, target int) [][]int {
	sort.Ints(nums) //先排序
	var res [][]int
	//计算数据大小
	n := len(nums)
	//参数合法性校验
	if n < 4 {
		return res
	}

	// 以下循环都是已排序后的数组为基础  所以有后递增的趋势 可以做剪枝操作 和去重操作

	//外层循环  注意n-3为止  在乡下循环无意义
	for i := 0; i < n-3; i++ {
		//剪枝操作 本层循环内i和最后几位想加达不到目标值 执行下一个
		if i > 0 && nums[i]+nums[n-1]+nums[n-2]+nums[n-3] < target {
			continue
		}
		//去重操作  本次循环内 重复的数直接下一个
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		for j := i + 1; j < n-2; j++ {
			//剪枝操作 本层循环内i和最后几位想加达不到目标值 执行下一个
			if j > i+1 && nums[i]+nums[n-1]+nums[n-2]+nums[j] < target {
				continue
			}
			//去重操作  本次循环内 重复的数直接下一个
			if j > i+1 && nums[j] == nums[j-1] {
				continue
			}
			//一下操作跟三数之和一样
			l := j + 1 //注意这里是j的加一
			r := n - 1
			for l < r {
				if nums[i]+nums[j]+nums[l]+nums[r] == target {
					res = append(res, []int{nums[i], nums[j], nums[l], nums[r]})
					//去重操作  本次循环内 重复的数直接下一个
					for l++; l < r && nums[l] == nums[l-1]; l++ {
					}
					//去重操作  本次循环内 重复的数直接下一个
					for r--; l < r && nums[r] == nums[r+1]; r-- {
					}
				} else if nums[i]+nums[j]+nums[l]+nums[r] < target {
					l++
				} else if nums[i]+nums[j]+nums[l]+nums[r] > target {
					r--
				}
			}
		}
	}
	return res
}
